CS157b Spring 2018Practice Midterm

Studying for one of my tests does involve some memorization. I believe this is an important skill. Often people waste a lot of time and fail to remember the things they are trying to memorize. Please use a technique that has been shown to work such as the method of loci. Other memorization techniques can be found off the Wiki Page for Moonwalking with Einstein. Given this, to study for the midterm I would suggest you:

• Start early and allow you self more than one day for study.
• Keep the bar to study low, if you have spare time, while doing something else, flip through your notes.
• Know how to do (by heart) all the practice problems.
• Go over your notes at least three times. On the second and third time try to see how much you can remember from the first time.
• Go over the homework problems.
• Try to create your own problems similar to the ones I have given and solve them.
• Skim the relevant sections from the book.
• If you want to study in groups, at this point you are ready to quiz each other.

The practice midterm is below. Here are some facts about the actual midterm: (a) It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test. (b) You should bring photo ID. (c) There will be more than one version of the test. Each version will be of comparable difficulty. (d) One problem (less typos) on the actual test will be from the practice test.

1. Draw a diagram of the memory hierarchy.
2. Give the elevator algorithm to schedule disk requests.
3. Suppose the odds that a disk drive fails in a given year is 1/5. Suppose further we have one data disk and two back up mirrors. What is the mean time till data lost if it takes 4 hours to replace a broken drive?
4. What is pointer swizzling? Briefly explain and give a concrete example of a block before and after pointer swizzling and an example situation where a swizzled pointer might be followed.
5. Explain with steps and an example how record insertion within a block is handled in the sorted records case.
6. Define the following terms: (a) Sequential file, (b) dense index, (c) clustered index.
7. What is the ISAM record format? Briefly describe the column schema of the sqlite_master table.
8. Give an example of a kd-tree with more than 4 leaves that queries at least three distinct attributes and which queries at least one of these twice. Explain how a look up could be performed on this tree.
9. Explain and give an example of how two pass sorting can be used to do duplicate elimination.
10. Suppose the block size was 8192, where 192 bytes are used for header info. Suppose had a 2,000,000 tuple relation. Suppose tuple size goes from 40 bytes long to 10 bytes long after a projection. How many block would be needed to store all the tuple before and after doing this projection?